#include <bits/stdc++.h>
using namespace std;

//从后向前尝试交换，如果无法交换（降序），则变为升序即可

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        //被交换的最小值的index作为最外层
        for(int i=len-2; i>=0; --i){
            for(int j=len-1; j>i; --j){
                if(nums[j] > nums[i]){
                    swap(nums[i], nums[j]);
                    sort(nums.begin()+i+1, nums.end());
                    return;
                }
            }
        }
        // reverse(nums.begin(), nums.end());
        int half = len/2;
        for(int i=0; i<half; ++i){
            swap(nums[i], nums[len-i-1]);
        }
    }
};

int main(){
    Solution solution;
    vector<int> nums = {1, 3, 2};
    solution.nextPermutation(nums);
}